1. Field of the Invention
The present invention relates to the field of data processing systems. More particularly, the present invention relates to techniques for reaching consistent state in a multi-threaded data processing system.
2. Description of the Prior Art
A data processing apparatus will typically include a processor core that is operable to execute native instructions from a native instruction set. Some of the applications that may be run by the data processing apparatus may include multiple program threads, and it is possible that those program threads may consist of instructions that are not native instructions, and hence cannot directly be executed on the processor core. In such situations, it is known to provide an interpreter which is operable to determine for a current program thread instruction a sequence of native instructions to be executed by the processor core in order to execute that current program thread instruction.
One example of such an approach is where the program thread instructions are from an instruction set that uses a stack-based approach for storing and manipulating data items upon which those instructions act, whilst the native instructions executable by the processor core are from an instruction set that uses a register-based approach for storing and manipulating the data items.
One example of a stack-based instruction set is the Java Virtual Machine instruction set as specified by Sun Microsystems Inc. The Java programming language seeks to provide an environment in which computer software written in Java can be executed upon many different processing hardware platforms without having to alter the Java software. Another example of a stack-based instruction set is the Java Card instruction set as specified by Sun Microsystems Inc., which is a version of Java which has been designed for use within smart cards and similar devices, i.e. devices which are relatively cheap and consume relatively low power.
An example of register-based systems are the ARM processors produced by ARM Limited of Cambridge, England. ARM instructions execute operations (such as mathematical manipulations, loads, stores, etc) upon operands stored within registers of the processor specified by register fields within the instructions.
It is becoming more desirable for data processing systems designed to execute register-based instructions to support execution of stack-based instructions. An example of such a data processing system is described in UK patent application no. 0024404.6. As described in that patent application, stack-based instructions are converted into a sequence of operations to be executed by the processor core upon registers within a register bank. The data items on the stack that are required by those operations are stored from the stack into registers of the register bank so that they are available to the processor core.
When such a data processing system is operating in a multi-threaded environment, some events may occur that require a number of the program threads (typically all of the program threads) to be stopped at a point where they will all then be in a consistent state. Such events include garbage collection to free up space in the data heap shared by the program threads, thread switching when performed by software associated with the interpreter (rather than being performed at the operating system level), certain debug events, etc.
Since at the time the event occurred, each of the program threads may be part way through execution of a sequence of native instructions used to execute a current program thread instruction, it is not appropriate to immediately stop each of the program threads, since if that were done the state of one or more of the program threads may be in some intermediate state which would not be consistent with the state that would actually arise upon completion of execution of that current program thread instruction. For any particular program thread, a consistent state for that program thread is reached at points where a current program thread instruction has completed execution, and a next program thread instruction has not yet begun execution. It is possible for the consistent state to remain a few native instructions into the execution of a program thread instruction, if those instructions do not modify the state.
One way in which this problem has been addressed in prior art techniques is to provide a predetermined routine, also referred to herein as a rendezvous routine, which when executed for a particular program thread will cause the state of that thread to be stored from the processor core's internal memory (for example the processor core's working registers in the example of a register-based processor core) to a block of memory storing an execution environment for that program thread. This execution environment will typically be provided within a memory accessible by other threads, for example a portion of Random Access Memory (RAM) used to store the execution environment of each thread, and accessible by all threads. To ensure that this rendezvous routine is only actioned at a point where the state will be a consistent state, a known prior art technique is to include within the native instruction sequences associated with particular program thread instructions a sequence of native instructions that will conditionally cause a branch to the rendezvous routine if an event requiring the threads to be stopped has occurred.
When such an event does occur, a particular memory location is written with a particular value (also referred to herein as the “rendezvous flag”), and the purpose of the extra sequence of native instructions added to the native instruction sequences for particular program thread instructions is to cause the data at that memory location to be loaded into a register, for the contents of that register to be compared with the predetermined value, and for the process to branch to the rendezvous routine if the comparison indicates equality between the values (i.e. indicates that the memory location has been written with that particular value, thereby indicating that the thread needs to be stopped, and that accordingly execution of the rendezvous routine is appropriate). These extra native instructions are written such that the rendezvous flag is polled at the end of the native instruction sequences for particular program thread instructions since at that point the state will be in a consistent state (i.e. the corresponding program thread instruction will have completed execution).
As will be appreciated by those skilled in the art, this approach involves adding a number of instructions (in one known implementation three instructions) to the native instruction sequence for a number of the program thread instructions, and these extra instructions have to be executed each time that corresponding program thread instruction needs to be executed, irrespective of whether the rendezvous routine does in fact need to be performed. This significantly impacts the performance of execution of such program thread instructions.
Ideally, to enable the system to react most quickly to an event requiring the threads to be stopped, these extra native instructions would be added to the native instruction sequence for every program thread instruction. However, that would adversely impact the performance to an unacceptable degree, and accordingly a compromise approach is typically employed where these extra native instructions are only added to the native instruction sequences corresponding to certain program thread instructions, for example method invocation instructions, backwards branches, etc. The rationale behind this compromise approach is to choose some instructions so that the period between polling the rendezvous flag is not too great. For example, polling in backwards branches means that all loops include at least one check. As another example, some Virtual Machines (VMs) may require the rendezvous flag to be checked in some instructions to ensure correct operation.
Nevertheless, it will be appreciated that there is still overall a significant performance hit in execution of the multiple program threads, since these extra instructions will still be executed every time the relevant program thread instructions are executed and irrespective of whether an event has in fact arisen that requires the rendezvous routine to take place.
Accordingly, it would be desirable to provide an improved technique which, upon the occurrence of an event requiring the threads to be stopped, enables the rendezvous routine to be invoked by each thread when that thread's state is in a consistent state.